home *** CD-ROM | disk | FTP | other *** search
/ Mission 3 / Mission 3.zip / Mission 3.iso / texte / 7up_pd / grep.c < prev    next >
C/C++ Source or Header  |  1998-10-29  |  15KB  |  726 lines
  1. /* Suchen mit regulären Ausdrücken */
  2. /*****************************************************************************
  3. *
  4. *                                              7UP
  5. *                                         Modul: GREP.C
  6. *                             (c) by DECUS '80 & TheoSoft '91
  7. *
  8. *****************************************************************************/
  9. #include <portab.h>
  10. #include <stdio.h>
  11. #include <stdlib.h>
  12. #include <string.h>
  13. #include <ctype.h>
  14.  
  15. #if GEMDOS
  16. #include <ext.h>
  17. #endif
  18.  
  19. #include "alert.h"
  20.  
  21. void store(char);
  22.  
  23. int    compile(char *);
  24. char *cclass(char *,char *);
  25. char *grep(char *,char *,int *);
  26. char *pmatch(char *,char *,char *);
  27.  
  28. int    icompile(char *);
  29. char *icclass(char *,char *);
  30. char *igrep(char *,char *,int *);
  31. char *ipmatch(char *,char *,char *);
  32.  
  33. #define PMAX     128
  34.  
  35. #define CHAR     1
  36. #define BOL      2
  37. #define EOL      3
  38. #define ANY      4
  39. #define CLASS    5
  40. #define NCLASS  6
  41. #define STAR     7
  42. #define PLUS     8
  43. #define MINUS    9
  44. #define ALPHA    10
  45. #define DIGIT    11
  46. #define NALPHA  12
  47. #define PUNCT    13
  48. #define RANGE    14
  49. #define ENDPAT  15
  50. #define INTERP  16
  51. #define BOW      17
  52. #define EOW      18
  53.  
  54. char     *pp;
  55.  
  56. static char pbuf[PMAX];
  57. extern char alertstr[];
  58.  
  59. /*******************************************************/
  60.  
  61. int compile(char *source)
  62. /*
  63. char         *source;    /* Pattern to compile            */
  64. */
  65. /*
  66.  * Compile the pattern into global pbuf[]
  67.  */
  68. {
  69.     register char  *s;            /* Source string pointer      */
  70.     register char  *lp;          /* Last pattern pointer        */
  71.     register int    c;             /* Current character            */
  72.     int                o;             /* Temp                             */
  73.     char              *spp;         /* Save beginning of pattern */
  74.     char              *cclass();  /* Compile class routine      */
  75.  
  76.     s = source;
  77.     lp = pp = pbuf; /* lp inserted for TC ************************/
  78.     while ((c = *s++)!=0) {
  79.         /*
  80.          * STAR, PLUS and MINUS are special.
  81.          */
  82.         if (c == '*' || c == '+' || c == '-') {
  83.             if (pp == pbuf ||
  84.                   (o=pp[-1]) == BOL ||
  85.                   o == EOL ||
  86.                   o == STAR ||
  87.                   o == PLUS ||
  88.                   o == MINUS)
  89.                 return(FALSE);
  90.  
  91.             store(ENDPAT);
  92.             store(ENDPAT);
  93.             spp = pp;                    /* Save pattern end      */
  94.             while (--pp > lp)         /* Move pattern down     */
  95.                 *pp = pp[-1];          /* one byte                 */
  96.             *pp =    (c == '*') ? STAR :
  97.                 (c == '-') ? MINUS : PLUS;
  98.             pp = spp;                    /* Restore pattern end  */
  99.             continue;
  100.         }
  101.         /*
  102.          * All the rest.
  103.          */
  104.         lp = pp;            /* Remember start         */
  105.         switch(c) {
  106.  
  107.         case '^':
  108.             store(BOL);
  109.             break;
  110.  
  111.         case '$':
  112.             store(EOL);
  113.             break;
  114.  
  115.         case '.':
  116.             store(ANY);
  117.             break;
  118. /*
  119.         case '<':
  120.             store(BOW);
  121.             break;
  122.  
  123.         case '>':
  124.             store(EOW);
  125.             break;
  126. */
  127.         case '[':
  128.             s = cclass(source, s);
  129.             if(s==NULL)
  130.                 return(FALSE);
  131.             break;
  132.  
  133.         case ':':
  134.             if (*s) {
  135.                 c = *s++;
  136.                 switch(__tolower(c)) {
  137.  
  138.                 case 'a':
  139.                 case 'A':
  140.                     store(ALPHA);
  141.                     break;
  142.  
  143.                 case 'd':
  144.                 case 'D':
  145.                     store(DIGIT);
  146.                     break;
  147.  
  148.                 case 'n':
  149.                 case 'N':
  150.                     store(NALPHA);
  151.                     break;
  152.  
  153.                 case ' ':
  154.                     store(PUNCT);
  155.                     break;
  156. /* NEU */
  157.                 case '.':
  158.                     store(INTERP);
  159.                     break;
  160. /*      */
  161.                 default:
  162.                     return(FALSE);
  163.                 }
  164.                 break;
  165.             }
  166.             else
  167.                 return(FALSE);
  168.         case '\\':
  169.             if (*s)
  170.                 c = *s++;
  171.  
  172.         default:
  173.             store(CHAR);
  174.             store(c);
  175.         }
  176.     }
  177.     store(ENDPAT);
  178.     store(0);                     /* Terminate string      */
  179.     return(TRUE);
  180. }
  181.  
  182. /* keine Unterscheidung zwischen GROβ- und Kleinschreibweise */
  183. int icompile(char *source)
  184. /*
  185. char         *source;    /* Pattern to compile            */
  186. */
  187. /*
  188.  * Compile the pattern into global pbuf[]
  189.  */
  190. {
  191.     register char  *s;            /* Source string pointer      */
  192.     register char  *lp;          /* Last pattern pointer        */
  193.     register int    c;             /* Current character            */
  194.     int                o;             /* Temp                             */
  195.     char              *spp;         /* Save beginning of pattern */
  196.     char              *cclass();  /* Compile class routine      */
  197.  
  198.     s = source;
  199.     lp = pp = pbuf; /* lp inserted for TC ************************/
  200.     while ((c = *s++)!=0) {
  201.         /*
  202.          * STAR, PLUS and MINUS are special.
  203.          */
  204.         if (c == '*' || c == '+' || c == '-') {
  205.             if (pp == pbuf ||
  206.                   (o=pp[-1]) == BOL ||
  207.                   o == EOL ||
  208.                   o == STAR ||
  209.                   o == PLUS ||
  210.                   o == MINUS)
  211.                 return(FALSE);
  212.  
  213.             store(ENDPAT);
  214.             store(ENDPAT);
  215.             spp = pp;                    /* Save pattern end      */
  216.             while (--pp > lp)         /* Move pattern down     */
  217.                 *pp = pp[-1];          /* one byte                 */
  218.             *pp =    (c == '*') ? STAR :
  219.                 (c == '-') ? MINUS : PLUS;
  220.             pp = spp;                    /* Restore pattern end  */
  221.             continue;
  222.         }
  223.         /*
  224.          * All the rest.
  225.          */
  226.         lp = pp;            /* Remember start         */
  227.         switch(c) {
  228.  
  229.         case '^':
  230.             store(BOL);
  231.             break;
  232.  
  233.         case '$':
  234.             store(EOL);
  235.             break;
  236.  
  237.         case '.':
  238.             store(ANY);
  239.             break;
  240. /*
  241.         case '<':
  242.             store(BOW);
  243.             break;
  244.  
  245.         case '>':
  246.             store(EOW);
  247.             break;
  248. */
  249.         case '[':
  250.             s = icclass(source, s);
  251.             if(s==NULL)
  252.                 return(FALSE);
  253.             break;
  254.  
  255.         case ':':
  256.             if (*s) {
  257.                 c = *s++;
  258.                 switch(__tolower(c)) {
  259.  
  260.                 case 'a':
  261.                 case 'A':
  262.                     store(ALPHA);
  263.                     break;
  264.  
  265.                 case 'd':
  266.                 case 'D':
  267.                     store(DIGIT);
  268.                     break;
  269.  
  270.                 case 'n':
  271.                 case 'N':
  272.                     store(NALPHA);
  273.                     break;
  274.  
  275.                 case ' ':
  276.                     store(PUNCT);
  277.                     break;
  278. /* NEU */
  279.                 case '.':
  280.                     store(INTERP);
  281.                     break;
  282. /*      */
  283.                 default:
  284.                     return(FALSE);
  285.                 }
  286.                 break;
  287.             }
  288.             else
  289.                 return(FALSE);
  290.         case '\\':
  291.             if (*s)
  292.                 c = *s++;
  293.  
  294.         default:
  295.             store(CHAR);
  296.             store(__tolower(c));
  297.         }
  298.     }
  299.     store(ENDPAT);
  300.     store(0);                     /* Terminate string      */
  301.     return(TRUE);
  302. }
  303.  
  304. /*******************************************************/
  305.  
  306. static char *cclass(char *source, char *src)
  307. /*
  308. char         *source;    /* Pattern start -- for error msg.        */
  309. char         *src;        /* Class start              */
  310. */
  311. /*
  312.  * Compile a class (within [])
  313.  */
  314. {
  315.     register char    *s;          /* Source pointer     */
  316.     register char    *cp;         /* Pattern start      */
  317.     register int     c;            /* Current character */
  318.     int                 o;            /* Temp                  */
  319.  
  320.     s = src;
  321.     o = CLASS;
  322.     if (*s == '^') {
  323.         ++s;
  324.         o = NCLASS;
  325.     }
  326.     store(o);
  327.     cp = pp;
  328.     store(0);                                  /* Byte count        */
  329.     while (((c = *s++)!=0) && c!=']') {
  330.         if (c == '\\') {                     /* Store quoted char     */
  331.             if ((c = *s++) == '\0')        /* Gotta get something  */
  332.                 return(NULL);
  333.             else
  334.                 store(c);
  335.         }
  336.         else if (c == '-' &&
  337.                 (pp - cp) > 1 && *s != ']' && *s != '\0') {
  338.             c = pp[-1];                 /* Range start      */
  339.             pp[-1] = RANGE;            /* Range signal     */
  340.             store(c);                    /* Re-store start  */
  341.             c = *s++;                    /* Get end char and*/
  342.             store(c);        /* Store it          */
  343.         }
  344.         else {
  345.             store(c);        /* Store normal char */
  346.         }
  347.     }
  348.     if (c != ']')
  349.         s=NULL;
  350.     if ((c = (int)(pp - cp)) >= PMAX)
  351.         s=NULL;
  352.     if (c == 0)
  353.         s=NULL;
  354.     *cp = c;
  355.     return(s);
  356. }
  357.  
  358. /* keine Unterscheidung zwischen GROβ- und Kleinschreibweise */
  359. static char *icclass(char *source, char *src)
  360. /*
  361. char         *source;    /* Pattern start -- for error msg.        */
  362. char         *src;        /* Class start              */
  363. */
  364. /*
  365.  * Compile a class (within [])
  366.  */
  367. {
  368.     register char    *s;          /* Source pointer     */
  369.     register char    *cp;         /* Pattern start      */
  370.     register int     c;            /* Current character */
  371.     int                 o;            /* Temp                  */
  372.  
  373.     s = src;
  374.     o = CLASS;
  375.     if (*s == '^') {
  376.         ++s;
  377.         o = NCLASS;
  378.     }
  379.     store(o);
  380.     cp = pp;
  381.     store(0);                                  /* Byte count        */
  382.     while (((c = *s++)!=0) && c!=']') {
  383.         if (c == '\\') {                     /* Store quoted char     */
  384.             if ((c = *s++) == '\0')        /* Gotta get something  */
  385.                 return(NULL);
  386.             else
  387.                 store(__tolower(c));
  388.         }
  389.         else if (c == '-' &&
  390.                 (pp - cp) > 1 && *s != ']' && *s != '\0') {
  391.             c = pp[-1];                 /* Range start      */
  392.             pp[-1] = RANGE;            /* Range signal     */
  393.             store(c);                    /* Re-store start  */
  394.             c = *s++;                    /* Get end char and*/
  395.             store(__tolower(c));        /* Store it          */
  396.         }
  397.         else {
  398.             store(__tolower(c));        /* Store normal char */
  399.         }
  400.     }
  401.     if (c != ']')
  402.         s=NULL;
  403.     if ((c = (int)(pp - cp)) >= PMAX)
  404.         s=NULL;
  405.     if (c == 0)
  406.         s=NULL;
  407.     *cp = c;
  408.     return(s);
  409. }
  410.  
  411. /*******************************************************/
  412. static void store(char op)
  413. {
  414.     if (pp >= &pbuf[PMAX])
  415.     {
  416.          form_alert(1,Agrep[0]);
  417.     }
  418.     *pp++ = op;
  419. }
  420.  
  421. /*******************************************************/
  422.  
  423. static char *pmatch(char *lbuf, char *line, char *pattern)
  424. /*
  425. char                    *line;      /* (partial) line to match        */
  426. char                    *pattern;  /* (partial) pattern to match    */
  427. */
  428. {
  429.     register char    *l;          /* Current line pointer            */
  430.     register char    *p;          /* Current pattern pointer        */
  431.     register char    c;            /* Current character                */
  432.     char                *e;          /* End for STAR and PLUS match  */
  433.     int                 op;          /* Pattern operation                */
  434.     int                 n;            /* Class counter                     */
  435.     char                *are;        /* Start of STAR match             */
  436.  
  437.     l = line;
  438.     p = pattern;
  439.     while ((op = *p++) != ENDPAT) {
  440.         switch(op) {
  441.  
  442.         case CHAR:
  443.             if (*l++ != *p++)
  444.                 return(NULL);
  445.             break;
  446.  
  447.         case BOL:
  448.             if (l != lbuf)
  449.                 return(NULL);
  450.             break;
  451.  
  452.         case EOL:
  453.             if (*l != '\0')
  454.                 return(NULL);
  455.             break;
  456.  
  457.         case ANY:
  458.             if (*l++ == '\0')
  459.                 return(NULL);
  460.             break;
  461. /*
  462.         case BOW:
  463.             c = *l++;
  464.             if(!(c == ' ' && *l != ' '))
  465.                 return(NULL);
  466.             break;
  467.  
  468.         case EOW:
  469.             c = *l++;
  470.             if(!(c == ' ' && *(l-2L) != ' '))
  471.                 return(NULL);
  472.             break;
  473. */
  474.         case DIGIT:
  475.             if ((c = *l++) < '0' || (c > '9'))
  476.                 return(NULL);
  477.             break;
  478.  
  479.         case ALPHA:
  480.             c = __tolower(*l++); /* Ausnahme */
  481.             if (c < 'a' || c > 'z')
  482.                 return(NULL);
  483.             break;
  484.  
  485.         case NALPHA:
  486.             c = __tolower(*l++); /* Ausnahme */
  487.             if (c >= 'a' && c <= 'z')
  488.                 break;
  489.             else if (c < '0' || c > '9')
  490.                 return(NULL);
  491.             break;
  492.  
  493.         case PUNCT:
  494.             c = *l++;
  495.             if (c == 0 || c > ' ')
  496.                 return(NULL);
  497.             break;
  498. /* NEU */
  499.         case INTERP:
  500.             c = *l++;
  501.             if(!ispunct(c))
  502.                 return(NULL);
  503.             break;
  504. /*      */
  505.         case CLASS:
  506.         case NCLASS:
  507.             c = *l++;
  508.             n = *p++ & 0377;
  509.             do {
  510.                 if (*p == RANGE) {
  511.                     p += 3;
  512.                     n -= 2;
  513.                     if (c >= p[-2] && c <= p[-1])
  514.                         break;
  515.                 }
  516.                 else if (c == *p++)
  517.                     break;
  518.             } while (--n > 1);
  519.             if ((op == CLASS) == (n <= 1))
  520.                 return(NULL);
  521.             if (op == CLASS)
  522.                 p += n - 2;
  523.             break;
  524.  
  525.         case MINUS:
  526.             e = pmatch(lbuf, l, p); /* Look for a match     */
  527.             while (*p++ != ENDPAT); /* Skip over pattern    */
  528.             if (e)                        /* Got a match?          */
  529.                 l = e;                    /* Yes, update string  */
  530.             break;                        /* Always succeeds      */
  531.  
  532.         case PLUS:                      /* One or more ...      */
  533.             if ((l = pmatch(lbuf, l, p)) == NULL)
  534.                 return(NULL);          /* Gotta have a match  */
  535.         case STAR:                      /* Zero or more ...     */
  536.             are = l;                     /* Remember line start */
  537.             while (*l && ((e = pmatch(lbuf, l, p))!=NULL))
  538.                 l = e;                    /* Get longest match    */
  539.             while (*p++ != ENDPAT); /* Skip over pattern    */
  540.             while (l >= are) {        /* Try to match rest    */
  541.                 if ((e = pmatch(lbuf, l, p))!=NULL)
  542.                     return(e);
  543.                 --l;                      /* Nope, try earlier    */
  544.             }
  545.             return(NULL);              /* Nothing else worked */
  546. /*
  547.         default:
  548.             error("Cannot happen -- match");
  549.             exit(-1);
  550. */
  551.         }
  552.     }
  553.     return(l);
  554. }
  555.  
  556. /* keine Unterscheidung zwischen GROβ- und Kleinschreibweise */
  557. static char *ipmatch(char *lbuf, char *line, char *pattern)
  558. /*
  559. char                    *line;      /* (partial) line to match        */
  560. char                    *pattern;  /* (partial) pattern to match    */
  561. */
  562. {
  563.     register char    *l;          /* Current line pointer            */
  564.     register char    *p;          /* Current pattern pointer        */
  565.     register char    c;            /* Current character                */
  566.     char                *e;          /* End for STAR and PLUS match  */
  567.     int                 op;          /* Pattern operation                */
  568.     int                 n;            /* Class counter                     */
  569.     char                *are;        /* Start of STAR match             */
  570.  
  571.     l = line;
  572.     p = pattern;
  573.     while ((op = *p++) != ENDPAT) {
  574.         switch(op) {
  575.  
  576.         case CHAR:
  577.             if (__tolower(*l++) != *p++)
  578.                 return(NULL);
  579.             break;
  580.  
  581.         case BOL:
  582.             if (l != lbuf)
  583.                 return(NULL);
  584.             break;
  585.  
  586.         case EOL:
  587.             if (*l != '\0')
  588.                 return(NULL);
  589.             break;
  590.  
  591.         case ANY:
  592.             if (*l++ == '\0')
  593.                 return(NULL);
  594.             break;
  595. /*
  596.         case BOW:
  597.             c = *l++;
  598.             if(!(c == ' ' && *l != ' '))
  599.                 return(NULL);
  600.             break;
  601.  
  602.         case EOW:
  603.             c = *l++;
  604.             if(!(c == ' ' && *(l-2L) != ' '))
  605.                 return(NULL);
  606.             break;
  607. */
  608.         case DIGIT:
  609.             if ((c = *l++) < '0' || (c > '9'))
  610.                 return(NULL);
  611.             break;
  612.  
  613.         case ALPHA:
  614.             c = __tolower(*l++);
  615.             if (c < 'a' || c > 'z')
  616.                 return(NULL);
  617.             break;
  618.  
  619.         case NALPHA:
  620.             c = __tolower(*l++);
  621.             if (c >= 'a' && c <= 'z')
  622.                 break;
  623.             else if (c < '0' || c > '9')
  624.                 return(NULL);
  625.             break;
  626.  
  627.         case PUNCT:
  628.             c = *l++;
  629.             if (c == 0 || c > ' ')
  630.                 return(NULL);
  631.             break;
  632. /* NEU */
  633.         case INTERP:
  634.             c = *l++;
  635.             if(!ispunct(c))
  636.                 return(NULL);
  637.             break;
  638. /*      */
  639.         case CLASS:
  640.         case NCLASS:
  641.             c = __tolower(*l++);
  642.             n = *p++ & 0377;
  643.             do {
  644.                 if (*p == RANGE) {
  645.                     p += 3;
  646.                     n -= 2;
  647.                     if (c >= p[-2] && c <= p[-1])
  648.                         break;
  649.                 }
  650.                 else if (c == *p++)
  651.                     break;
  652.             } while (--n > 1);
  653.             if ((op == CLASS) == (n <= 1))
  654.                 return(NULL);
  655.             if (op == CLASS)
  656.                 p += n - 2;
  657.             break;
  658.  
  659.         case MINUS:
  660.             e = ipmatch(lbuf, l, p); /* Look for a match     */
  661.             while (*p++ != ENDPAT); /* Skip over pattern    */
  662.             if (e)                        /* Got a match?          */
  663.                 l = e;                    /* Yes, update string  */
  664.             break;                        /* Always succeeds      */
  665.  
  666.         case PLUS:                      /* One or more ...      */
  667.             if ((l = ipmatch(lbuf, l, p)) == NULL)
  668.                 return(NULL);          /* Gotta have a match  */
  669.         case STAR:                      /* Zero or more ...     */
  670.             are = l;                     /* Remember line start */
  671.             while (*l && ((e = ipmatch(lbuf, l, p))!=NULL))
  672.                 l = e;                    /* Get longest match    */
  673.             while (*p++ != ENDPAT); /* Skip over pattern    */
  674.             while (l >= are) {        /* Try to match rest    */
  675.                 if ((e = ipmatch(lbuf, l, p))!=NULL)
  676.                     return(e);
  677.                 --l;                      /* Nope, try earlier    */
  678.             }
  679.             return(NULL);              /* Nothing else worked */
  680. /*
  681.         default:
  682.             error("Cannot happen -- match");
  683.             exit(-1);
  684. */
  685.         }
  686.     }
  687.     return(l);
  688. }
  689.  
  690. /*******************************************************/
  691.  
  692. char *grep(char *str, char *lp, int *len)
  693. /*
  694.  * Match the current line (in lbuf[]), return 1 if it does.
  695.  */
  696. {
  697.     char *ep;
  698.     for (lp = str; *lp; lp++) {
  699.         if (ep=pmatch(str, lp, pbuf))
  700.         {
  701.             *len=ep-lp;
  702.             return(lp);
  703.         }
  704.     }
  705.     *len=0;
  706.     return(NULL);
  707. }
  708.  
  709. /* keine Unterscheidung zwischen GROβ- und Kleinschreibweise */
  710. char *igrep(char *str, char *lp, int *len)
  711. /*
  712.  * Match the current line (in lbuf[]), return 1 if it does.
  713.  */
  714. {
  715.     char *ep;
  716.     for (lp = str; *lp; lp++) {
  717.         if (ep=ipmatch(str, lp, pbuf))
  718.         {
  719.             *len=ep-lp;
  720.             return(lp);
  721.         }
  722.     }
  723.     *len=0;
  724.     return(NULL);
  725. }
  726.